<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>YTU 3413_ 小姬小姬小姬.md | 蓝湖畔淅淅沥沥的雨</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。  题目描述 小姬最近开始研究起了曼哈顿距离，因为他厌倦了欧氏距离的学习。 我们知道，平面内 (x1,">
<meta property="og:type" content="article">
<meta property="og:title" content="YTU 3413_ 小姬小姬小姬.md">
<meta property="og:url" content="http://example.com/1111/11/11/YTU%203413_%20%E5%B0%8F%E5%A7%AC%E5%B0%8F%E5%A7%AC%E5%B0%8F%E5%A7%AC/index.html">
<meta property="og:site_name" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。  题目描述 小姬最近开始研究起了曼哈顿距离，因为他厌倦了欧氏距离的学习。 我们知道，平面内 (x1,">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="1111-11-11T03:06:11.000Z">
<meta property="article:modified_time" content="2022-05-06T07:32:49.942Z">
<meta property="article:author" content="StarsWhisper">
<meta property="article:tag" content="OldBlog(Before20220505)">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="蓝湖畔淅淅沥沥的雨" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

  
<link rel="stylesheet" href="/plugin/bganimation/bg.css">

  

  <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">
<meta name="generator" content="Hexo 6.1.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <div class="outer">
        <div class="widget-wrap mobile-header">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

        <section id="main"><article id="post-YTU 3413_ 小姬小姬小姬" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/YTU%203413_%20%E5%B0%8F%E5%A7%AC%E5%B0%8F%E5%A7%AC%E5%B0%8F%E5%A7%AC/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      YTU 3413_ 小姬小姬小姬.md
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E7%9E%8E%E6%90%9E/">瞎搞</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="题目描述"><a class="markdownIt-Anchor" href="#题目描述"></a> 题目描述</h2>
<p>小姬最近开始研究起了曼哈顿距离，因为他厌倦了欧氏距离的学习。</p>
<p>我们知道，平面内 (x1,y1) 与 (x2,y2) 的曼哈顿距离被定义为这两点在标准坐标系上的绝对轴距之和，即 |x1−x2|+|y1−y2|。</p>
<p>对于小姬来讲，他可以很容易的算出给定平面内任意多个点之间的曼哈顿距离，但是千千给小姬出了一个问题：假如我有 n(n−1)2 个数，它们分别代表平面中 n<br />
个点之间的曼哈顿距离，你能告诉我这 n 个点的位置么？</p>
<p>随后的几天，小姬开始困惑了，因为他想来想去也只会算当 n=2 的情形，于是便去找千千诉苦，看到这样的情形，千千只好答应降低难度，只要你算出 n=3<br />
的情形便可以啦。</p>
<p>你能帮小姬解决这个问题么？</p>
<h2 id="输入"><a class="markdownIt-Anchor" href="#输入"></a> 输入</h2>
<p>输入只有一行，包含三个正整数 a,b,c (1≤a,b,c≤100)，分别代表平面中 3 个点两两之间的曼哈顿距离。（保证输入数据有解）</p>
<h2 id="输出"><a class="markdownIt-Anchor" href="#输出"></a> 输出</h2>
<p>输出满足题意的三个点的坐标（要求<br />
0≤|x|,|y|≤105），每个点的坐标占一行，可以以任意的顺序输出，若存在多解的情况，输出任意一组即可。（如果你的答案计算出的结果与真实值相差 10−6<br />
以内则被认为是正确的）</p>
<h2 id="样例输入"><a class="markdownIt-Anchor" href="#样例输入"></a> 样例输入</h2>
<p>1 1 2</p>
<h2 id="样例输出"><a class="markdownIt-Anchor" href="#样例输出"></a> 样例输出</h2>
<p>0.000000 0.000000<br />
1.000000 0.000000<br />
0.000000 1.000000</p>
<h2 id="思路"><a class="markdownIt-Anchor" href="#思路"></a> 思路</h2>
<p>在这三个曼哈顿距离中任取一个d，它一定表示两点之间的曼哈顿距离<br />
设其中一个点为原点，则另一个点一定在以原点为中心距离远点曼哈顿距离为d的菱形（正方形）上。<br />
其他两个输入值，其中有一个值是于原点相关的曼哈顿距离，而这个值对应的点也应该是围绕原点的一个菱形（正方形）<br />
。<br />
不妨先假设其中一个值是与原点相关的曼哈顿距离，只要第三个值（原点除外的其他两点的曼哈顿距离）在区间【两菱形之间点的最短距离，两菱形点的最长距离】范围之内，则必定可以求解，如果不满足，则最后剩下的值才是与原点关联的值<br />
。<br />
这样我们就可以先直接定死两个点，求第三个点。<br />
先说两个菱形大小不一样的情况：<br />
如下图，（这个图我只看了右边）<br />
1.我定的点是（0，0）和小菱形最上端的点（0，x）<br />
图中上方表示红线（0，x）和求解点有最短距离时求解点存在的范围，在这一线段上（0，x）和求解点的曼哈顿距离相等，这个最短距离为abs（与原点相关的连个曼哈顿距离只差），若不关联原点的曼哈顿距离就是最短距离，则随便取红线上的一点就是答案<br />
2.同理，下方红线表示（0，x）和所求点曼哈顿距离最长的范围，若不关联原点的曼哈顿距离等于最长距离，则随便在下方红线上取一点就是答案<br />
3.在蓝线上（0，x）到求解点的曼哈顿距离递增<br />
我们可以先把求解点定在上方红线的最下边，这时求解点与（0，x）的曼哈顿距离为最短距离，然后再将求解点向下偏移，令两点之间的曼哈顿距离增长（不关联原点的曼哈顿距离-<br />
最短距离），得到的点就是答案（斜率都是1或-1呀）<br />
![在这里插入图片描述](<a target="_blank" rel="noopener" href="https://img-blog.csdnimg.cn/20201028223150512.png?x-oss-">https://img-blog.csdnimg.cn/20201028223150512.png?x-oss-</a><br />
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70#pic_center)<br />
如果两个菱形大小一样，最上方的红线就会变成一个点，其余思路不变，所以这种情况不用另外考虑 <s>战吼：放一个P</s></p>
<h2 id="代码"><a class="markdownIt-Anchor" href="#代码"></a> 代码</h2>
<p>一遍过的，里面有些冗余的东西写出来了根本没用上，比如那个结构体的点</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;string&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Edge</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">float</span> x,y;</span><br><span class="line">&#125;p1,p2,p3;</span><br><span class="line"><span class="type">int</span> a,b,c;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">fun</span><span class="params">(<span class="type">float</span> p,<span class="type">float</span> q,<span class="type">float</span> w)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">float</span> x,y,px,py,left;</span><br><span class="line">    <span class="keyword">if</span>(p&lt;q) x=p,y=q;</span><br><span class="line">    <span class="keyword">else</span> x=q,y=p;</span><br><span class="line">    <span class="keyword">if</span> (w == std::<span class="built_in">abs</span>(p-q))</span><br><span class="line">    &#123;</span><br><span class="line">        px=<span class="number">0</span>;</span><br><span class="line">        py=y;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span>(w == p+q)</span><br><span class="line">    &#123;</span><br><span class="line">        px=<span class="number">0</span>;</span><br><span class="line">        py=-y;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="type">float</span> tmp=std::<span class="built_in">abs</span>(p-q);</span><br><span class="line">        px=tmp,py=x;</span><br><span class="line">        left=w-tmp;</span><br><span class="line">        left/=<span class="number">2</span>;</span><br><span class="line">        px+=left;</span><br><span class="line">        py-=left;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%.6f %.6f\n&quot;</span>,<span class="number">0.0</span>,<span class="number">0.0</span>);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%.6f %.6f\n&quot;</span>,<span class="number">0.0</span>,x);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%.6f %.6f\n&quot;</span>,px,py);</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    std::cin &gt;&gt; a &gt;&gt; b &gt;&gt; c;</span><br><span class="line">    p1.x=p1.y=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span>(c&gt;= std::<span class="built_in">abs</span>(a-b) &amp;&amp; c&lt;= a+b)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">fun</span>(a,b,c);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">fun</span>(a,c,b);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/YTU%203413_%20%E5%B0%8F%E5%A7%AC%E5%B0%8F%E5%A7%AC%E5%B0%8F%E5%A7%AC/" data-id="cl2uhoebg000be4j35wly2t3g" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/1111/11/11/Splay/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">上一篇</strong>
      <div class="article-nav-title">
        
          Splay.md
        
      </div>
    </a>
  
  
    <a href="/1111/11/11/git%20github%20%E5%88%9D%E7%94%A8/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">下一篇</strong>
      <div class="article-nav-title">git github 初用.md</div>
    </a>
  
</nav>

  
</article>



</section>
        
          <aside id="sidebar">
  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <h1 class="blog-title">蓝湖畔淅淅沥沥的雨</h1>
    <h2 class="blog-subtitle">All tragedy erased, I see only wonders...</h2>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>



    <div class="social-link">
      
        <a class="hvr-bounce-in" href="https://github.com/Wldcmzy" target="_blank" title="Github">
          Github
        </a>
      
        <a class="hvr-bounce-in" href="https://blog.csdn.net/wldcmzy" target="_blank" title="CSDN">
          CSDN
        </a>
      
        <a class="hvr-bounce-in" href="https://space.bilibili.com/83743701" target="_blank" title="bilibili(无技术和学习内容)">
          bilibili(无技术和学习内容)
        </a>
      
    </div>

    <div class="friend-link">
      <h2>友情链接</h2>
      
        <a class="hvr-bounce-in" href="https://shanamaid.github.io/" target="_blank" title="夏娜主题作者的博客">
          夏娜主题作者的博客
        </a>
      
    </div>
  </div>
</div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy;2021 - 2022 StarsWhisper<br>
      由<a href="http://hexo.io/" target="_blank">Hexo</a>强力驱动 | 
      主题-<a target="_blank" rel="noopener" href="https://github.com/ShanaMaid/hexo-theme-shana">Shana</a>(但是魔改)
      
    </div>
    
  </div>
</footer>
    </div>
    

<script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
<script src="//apps.bdimg.com/libs/wow/0.1.6/wow.min.js"></script>
<script>
new WOW().init();
</script>   


  
<link rel="stylesheet" href="/plugin/fancybox/jquery.fancybox.css">

  
<script src="/plugin/fancybox/jquery.fancybox.pack.js"></script>




  
<link rel="stylesheet" href="/plugin/galmenu/GalMenu.css">

  
<script src="/plugin/galmenu/GalMenu.js"></script>

  <div class="GalMenu GalDropDown">
      <div class="circle" id="gal">
        <div class="ring">
          
            <a href="/announcement" title="" class="menuItem">公告</a>
          
            <a href="/tags" title="" class="menuItem">标签</a>
          
            <a href="/categories" title="" class="menuItem">分类</a>
          
            <a href="/archives" title="" class="menuItem">归档</a>
          
            <a href="/knightabout" title="" class="menuItem">关于</a>
          
            <a href="/bridges" title="" class="menuItem">传送门</a>
          
        </div>
        
          <audio id="audio" src="#"></audio>
        
      </div> 
</div>
<div id="overlay" style="opacity: 1; cursor: pointer;"></div>
  <script type="text/javascript">var items = document.querySelectorAll('.menuItem');
    for (var i = 0,
    l = items.length; i < l; i++) {
      items[i].style.left = (50 - 35 * Math.cos( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%";
      items[i].style.top = (50 + 35 * Math.sin( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%"
    }</script>
<script type="text/javascript">
  $(document).ready(function() {
    $('body').GalMenu({
      'menu': 'GalDropDown'
    })
  });
</script>

  <section class="hidden-xs"> 
  <ul class="cb-slideshow"> 
    <li><span>苟利</span></li> 
    <li><span>国家</span></li> 
    <li><span>生死以</span></li> 
    <li><span>岂能</span></li> 
    <li><span>祸福</span></li> 
    <li><span>趋避之</span></li> 
  </ul>
</section>

<script src="/js/script.js"></script>




  </div>
</body>
</html>